package com.lw.leetcode.back.b;

import com.lw.test.util.Utils;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 2572. 无平方子集计数
 *
 * @author liw
 * @version 1.0
 * @date 2023/2/20 9:51
 */
public class SquareFreeSubsets {

    public static void main(String[] args) {
        SquareFreeSubsets test = new SquareFreeSubsets();

        // 3
//        int[] arr = {3, 4, 4, 5};

        // 11
//        int[] arr = {24, 8, 9, 4, 7, 20, 19, 28, 14, 17};

        // 11
//        int[] arr = {7, 14, 1, 1};

        //
        int[] arr = Utils.getArr(1000, 1, 31);

        int i = test.squareFreeSubsets(arr);
        System.out.println(i);
    }

    private int[] arr;
    private int[] counts;
    private int[][] items;
    private long sum = 0;

    public int squareFreeSubsets(int[] nums) {
        int size = 31;
        this.arr = new int[size];
        this.counts = new int[size];
        items = new int[size][];

        items[1] = new int[]{1};
        items[2] = new int[]{2};
        items[3] = new int[]{3};
        items[5] = new int[]{5};
        items[6] = new int[]{2, 3};
        items[7] = new int[]{7};
        items[10] = new int[]{2, 5};
        items[11] = new int[]{11};
        items[13] = new int[]{13};
        items[14] = new int[]{2, 7};
        items[15] = new int[]{3, 5};
        items[17] = new int[]{17};
        items[19] = new int[]{19};
        items[21] = new int[]{3, 7};
        items[22] = new int[]{2, 11};
        items[23] = new int[]{23};
        items[26] = new int[]{2, 13};
        items[29] = new int[]{29};
        items[30] = new int[]{2, 3, 5};

        for (int num : nums) {
            arr[num]++;
        }
        if (arr[1] != 0) {
            int v = arr[1];
            long e = 1;
            while (v > 0) {
                e = (e << 1) % 1000000007;
                v--;
            }
            arr[1] = (int) (e - 1 < 0 ? e - 1 + 1000000007 : e - 1);
        }
        Set<Integer> set = new HashSet<>();
        for (int i = 1; i < size; i++) {
            if (items[i] == null || arr[i] == 0) {
                continue;
            }
            set.clear();
            for (int item : items[i]) {
                set.add(item);
            }
            counts[0] = i;
            find(i, set, 1, 1);
        }
        return (int) sum;
    }

    private void find(int t, Set<Integer> set, int index, int count) {
        if (index == t) {
            long r = 1;
            for (int j = 0; j < count; j++) {
                r = r * arr[counts[j]] % 1000000007;
            }
            sum = (sum + r) % 1000000007;
            return;
        }
        if (items[index] == null || arr[index] == 0) {
            find(t, set, index + 1, count);
            return;
        }
        boolean f = true;
        for (int i : items[index]) {
            if (set.contains(i)) {
                f = false;
                break;
            }
        }
        find(t, set, index + 1, count);
        if (f) {
            counts[count] = index;
            for (int item : items[index]) {
                set.add(item);
            }
            find(t, set, index + 1, count + 1);
            for (int item : items[index]) {
                set.remove(item);
            }
        }
    }

}
